package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/5 10:04 下午
 */
public class 剑指_Offer_30_包含min函数的栈 {

}

/**
 * 数组实现栈+动态规划
 */
class MinStack {
    int[] elements;
    int[] dp;
    int size;

    int minIndex;

    /** initialize your data structure here. */
    public MinStack() {
        elements = new int[20000];
        dp = new int[20000];
        size = 0;
    }

    public void push(int x) {
        if (size == 0) {
            minIndex = 0;
            dp[size] = 0;
        }

        elements[size] = x;
        if (size > 0) {
            dp[size] = x > elements[dp[size -1]] ? dp[size -1] : size;
        }
        size++;
    }

    public void pop() {
        if (size < 1) {
            return;
        }
        size--;
    }

    public int top() {
        if (size < 1) {
            return 0;
        }
        return elements[size -1];
    }

    public int min() {
        return elements[dp[size-1]];
    }
}

/**
 * 数组实现栈+动态规划+动态扩容
 */
class MinStack2 {
    int[] elements;
    int[] dp;
    int size;
    int cap;

    int minIndex;
    final int MAX_CAP = 20000;

    /** initialize your data structure here. */
    public MinStack2() {
        cap = 100;
        elements = new int[cap];
        dp = new int[cap];
        size = 0;
    }

    public void push(int x) {
        if (size == 0) {
            minIndex = 0;
            dp[size] = 0;
        }

        if (size >= cap) {
            recapArray();
        }

        elements[size] = x;
        if (size > 0) {
            dp[size] = x > elements[dp[size -1]] ? dp[size -1] : size;
        }
        size++;
    }

    private void recapArray() {
        cap = this.cap << 1;
        if (cap > MAX_CAP) {
            cap = MAX_CAP;
        }
        int[] newElements = new int[cap];
        System.arraycopy(elements,0,newElements,0,size);
        int[] newDp = new int[cap];
        System.arraycopy(dp,0,newDp,0,size);
        elements = newElements;
        dp = newDp;
    }

    public void pop() {
        if (size < 1) {
            return;
        }
        size--;
    }

    public int top() {
        if (size < 1) {
            return 0;
        }
        return elements[size -1];
    }

    public int min() {
        return elements[dp[size-1]];
    }
}